package arithmetic.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author jiangfeng 2022/3/19 10:40
 */
public class QuickSort5 {

    public static void main(String[] args) {
        int[] arrTest = {3,6,2,3,7,9,8,5};
        //
        sort(arrTest,0,arrTest.length-1);
        System.out.println(Arrays.toString(arrTest));

        int size = 200;
        int[] arr = new int[size];
        Random r = new Random(1);
        for (int i = 0; i < size; i++) {
            arr[i] = r.nextInt(1000);
        }

        System.out.println(Arrays.toString(arr));
        sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] a,int l,int r){
        if(l>=r){
            return;
        }
        int pivot = l;
        // 注意循环 不能从0 开始,从l开始,r结束, 要小于等于中等于号可以没必要 因为以最后一个为基准
        for (int i = l; i < r; i++) {
            if(a[i]<a[r]){ // 基准值放最右
                swap(a,pivot++,i);
            }
        }
        swap(a,pivot,r);
        sort(a,l,pivot-1);
        sort(a,pivot+1,r);

    }

    public static void swap(int[] a,int l,int r){
        if(l==r) return;
        int temp = a[l];
        a[l] = a[r];
        a[r] = temp;
    }


}
